package com.javabasic.algorithm.leetcode;

import java.util.HashMap;
import java.util.Objects;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/10/26 10:11 下午
 * @see [496. Next Greater Element I](https://leetcode-cn.com/problems/next-greater-element-i/)
 */
public class NextGreaterElementI {

    /**
     * 动态规划：
     * dp[i]=j,表示nums2数组下标为i的位置，下一个比它打得数的位置下标为j
     * 从后往前推:
     * dp[i] = i+1  (nums2[i] < nums[i+1])
     * dp[i] = dp[i+1]  (nums2[i] > nums[dp[i+1]],如果不满足就一直递归往后找)
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len = nums2.length;
        int[] dp = new int[len];
        /**
         * 记录数字和下标的位置关系，前提是数组中的数据是不重复的
         */
        HashMap<Integer, Integer> numToIndex = new HashMap<>(16);
        for (int i = 0; i < len; i++) {
            dp[i] = -1;
            numToIndex.put(nums2[i],i);
        }
        for (int i = len-2; i >= 0; i--) {
            int tag = i+1;
            while (tag != -1) {
                if (nums2[tag] > nums2[i]) {
                    dp[i] = tag;
                    break;
                } else {
                    tag = dp[tag];
                }
            }
            if (tag == -1) {
                dp[i] = tag;
            }
        }

        len = nums1.length;
        int numsOneIndex = 0;
        for (int i = 0; i < len; i++) {
            numsOneIndex = dp[numToIndex.getOrDefault(nums1[i], 0)];
            if (Objects.equals(-1,numsOneIndex)) {
                nums1[i] = nums2[numsOneIndex];
            } else {
                nums1[i] = numsOneIndex;
            }
        }
        return nums1;
    }
}
